一些常见数列的生成函数推导

一些常见数列的生成函数推导，URL是瞎打的

数列的生成函数可以涵盖原数列的很多信息。它可以用来代入求值化简一些级数的求和，也可以配合多项式全家桶使用以反求原数列。

本文仅仅给出了几个常见数列的生成函数的推导，并没有讲其他的内容，由于讲这玩意的博客非常多，大家去找几篇看就好了。

斐波那契数列F的生成函数

非常简单，就当热身吧。

递推式

$F_n=F_{n-1}+F_{n-2}$

边界

$F_0=F_1=1$

（注意，这里不是常见的$F_0=0$）

通项式

$F_n=\frac{\phi^{n+1}-(-\phi)^{-n-1}}{\sqrt 5},\phi=\frac{\sqrt 5+1}{2}$

生成函数

$\begin{aligned} G(x)&=\sum_{n=0}^\infty F_nx^n\cr &=1+x+\sum_{n=2}^\infty (F_{n-1}+F_{n-2})x^n\cr &=1+xG(x)+x^2G(x)\cr &=\frac{1}{1-x-x^2} \end{aligned}$

备注

不会真的有人用多项式求逆去求斐波那契数列吧。

代入求值倒是有些用途，比如这个东西，我在下面给出了一种生成函数代入求值的方法，可以说非常简便了。

卡特兰数C的生成函数

卡特兰数的第$n$项是$n$对括号匹配的方案数。

递推式

$C_n=\sum_{i=0}^{n-1}C_{i}C_{n-i-1}$

边界

$C_0=1$

通项式

$C_n=C(2n,n)-C(2n,n-1)$

生成函数

$\begin{aligned} G(x)&=\sum_{n=0}^\infty C_nx^n\cr &=1+\sum_{n=1}^\infty x^n\sum_{i=0}^{n-1}C_{i}C_{n-i-1}\cr &=1+\sum_{n=1}^\infty x\sum_{i=0}^{n-1}C_{i}x^iC_{n-i-1}x^{n-i-1}\cr &=1+x(\sum_{i=0}^\infty C_ix^i)^2\cr &=1+xG(x)^2\cr &=\frac{1\pm\sqrt{1-4x}}{2x} \end{aligned}$

这个函数应该是一个单调增函数，由此可以确定正负号那里应该取负号。

$G(x)=\frac{1-\sqrt{1-4x}}{2x}$

备注

卡特兰数拥有简单的通项公式，所以也不用这个玩意去求原数列。它的代入求值可以解决一些概率和期望的问题。

组合数C(n,m)的第m列的生成函数

这里是对一个三角形数列的某一列求生成函数，存在递推关系。这里用$G_m$表示第$m$列的生成函数。

递推式

$C(n,m)=C(n-1,m-1)+C(n-1,m)$

边界

$C(n,0)=1,n<m\Rightarrow C(n,m)=0$

通项式

$C(n,m)=\frac{n!}{m!(n-m)!}$

生成函数

当$m=0$时可直接求出$G_0(x)=\frac{1}{1-x}$。当$m>0$时：

$\begin{aligned} G_m(x)&=\sum_{n=0}^\infty C(n,m)x^n\cr &=\sum_{n=m}^\infty (C(n-1,m-1)+C(n-1,m))x^n\cr &=x\sum_{n=m}^\infty C(n-1,m-1)x^{n-1}+x\sum_{n=m}^\infty C(n-1,m)x^{n-1}\cr &=xG_{m-1}(x)+xG_m(x)\cr &=\frac{x}{1-x}G_{m-1}(x)\cr &=\frac{x^m}{(1-x)^{m+1}} \end{aligned}$

第二类斯特林数S_2(n,m)的第m列的指数生成函数

第二类斯特林数是$n$个元素划分成$m$个集合的方案数。

数列$a$的指数生成函数是数列$b_n=\frac{a_n}{n!}$的生成函数，我们用$\hat{G}$来表示它。

递推式

$S_2(n,m)=S_2(n-1,m-1)+mS_2(n-1,m)$

边界

$S_2(n,0)=[n=0],n<m\Rightarrow S_2(n,m)=0$

通项式

$S_2(n,m)=\frac{1}{m!}\sum_{i=0}^m(-1)^{m+i}C(m,i)i^n$

生成函数

当$m=0$时可直接求出$\hat{G}_0(x)=1$。当$m>0$时：

$\begin{aligned} \hat{G}_m(x)&=\sum_{n=0}^\infty \frac{1}{n!}S_2(n,m)x^n\cr &=\sum_{n=m}^\infty \frac{1}{n!}(S_2(n-1,m-1)+mS_2(n-1,m))x^n\cr &=\int \hat{G}_{m-1}(x)dx+m\int \hat{G}_{m}(x)dx+c\cr &=\frac{1}{m!}(e^x-1)^m \end{aligned}$

这里省略了怎么解这个带积分的方程（其实我也不太会QAQ），可以代入结果检验是正确的。其中的积分常量$c$可以根据$\hat{G}(0)=0$确定。

备注

虽然第二类斯特林数有通项公式，但是不够简单。这回体现出用多项式全家桶求原数列的作用了，洛谷上还有模板题。看完这篇博客就可以去水黑题了，多好。

贝尔数B的指数生成函数

贝尔数是$n$个元素划分成若干个集合的方案数。

递推式

$B(n)=\sum_{i=0}^{n-1}C(n-1,i)B(i)$

边界

$B(0)=1$

生成函数

$\begin{aligned} \hat{G}(x)&=\sum_{n=0}^\infty \frac{1}{n!}B(n)x^n\cr &=\sum_{n=0}^\infty \frac{1}{n!}x^n\sum_{i=0}^{n-1}C(n-1,i)B(i)\cr &=\sum_{n=0}^\infty \frac{1}{n}x\sum_{i=0}^{n-1}\frac{1}{i!}B(i)x^i\frac{1}{(n-i-1)!}x^{n-i-1}\cr &=\int \hat{G}(x)e^xdx+c\cr &=e^{e^x-1} \end{aligned}$

这个积分方程可以两边求导然后凑出来解出$\hat{G}(x)=e^{e^x+c}$，根据$\hat{G}(0)=1$确定那个常数是$-1$。

备注

我们知道贝尔数就是第二类斯特林数一整行的和，因此我们可以把第二列斯特林数所有列的指数生成函数加起来得到贝尔数的指数生成函数：

$\hat{G}(x)=\sum_{m=0}^\infty \frac{1}{m!}(e^x-1)^m=e^{e^x-1}$

得出的结果是一样的。

第一类斯特林数S_1(n,m)的第m列的指数生成函数

第一类斯特林数是$n$个元素组成成$m$个环排列的方案数。

递推式

$S_1(n,m)=S_1(n-1,m-1)+(n-1)S_1(n-1,m)$

边界

$S_1(n,0)=[n=0],n<m\Rightarrow S_1(n,m)=0$

生成函数

当$m=0$时可直接求出$\hat{G}_0(x)=1$。当$m>0$时：

$\begin{aligned} \hat{G}_m(x)&=\sum_{n=0}^\infty \frac{1}{n!}S_1(n,m)x^n\cr &=\sum_{n=m}^\infty \frac{1}{n!}(S_1(n-1,m-1)+(n-1)S_1(n-1,m))x^n\cr &=\int \hat{G}_{m-1}(x)dx+m\int \sum_{n=m}^\infty \frac{1}{n!}nS_1(n,m)x^ndx+c\cr &=\int \hat{G}_{m-1}(x)dx+\int x\hat{G}_{m}'(x)dx+c\cr &=\frac{1}{m!}\ln(\frac{1}{1-x})^m \end{aligned}$

这个积分方程可以两边求导，移项，再积分，得到

$\hat{G}_m(x)=\int \frac{\hat{G}_{m-1}(x)}{1-x}dx+c$

会积分就能归纳出结果，积分常量根据$\hat{G}(0)=0$确定。然而我不会积分，可以代入验证结果是正确的。

备注

又可以去水另一道模板题了，真好。

第一类斯特林数一行的和就是$n$的阶乘，所以把所有列的指数生成函数加起来我们就能得到数列$a_n=n!$的指数生成函数，也就是$a_n=1$的生成函数：

$\hat{G}(x)=\sum_{m=0}^\infty \frac{1}{m!}\ln(\frac{1}{1-x})^m=e^{\ln(\frac{1}{1-x})}=\frac{1}{1-x}$

和预期的结果一样，这进一步验证了我们推出的指数生成函数应该是正确的。

完全二分图匹配数T(n,m)的第m列的指数生成函数

$T(n,m)$是两侧分别有$n$和$m$个点的完全二分图的匹配个数。

递推式

$T(n,m)=mT(n-1,m-1)+T(n-1,m)$

边界

$T(n,0)=T(0,m)=1$

通项式

$T(n,m)=\sum_{i=0}^{\min(n,m)}C(n,i)C(m,i)i!$

生成函数

当$m=0$时可直接求出$\hat{G}_0(x)=e^x$。当$m>0$时：

$\begin{aligned} \hat{G}_m(x)&=\sum_{n=0}^\infty \frac{1}{n!}T(n,m)x^n\cr &=\sum_{n=m}^\infty \frac{1}{n!}(mT(n-1,m-1)+T(n-1,m))x^n\cr &=m\int \hat{G}_{m-1}(x)dx+\int \hat{G}_{m}(x)dx+c\cr &=(x+1)^me^x \end{aligned}$

一个表格

递推式形如$A(n,m)=pA(n-1,m-1)+qA(n-1,m)$的三角形第$m$列的指数型生成函数：

数列	$p$	$q$	$\hat{G}_m=$	$\hat{G}_0$	$\hat{G}_m(0),m>0$	封闭形式
组合数	$1$	$1$	$\int \hat{G}_{m-1}(x)dx+\int \hat{G}_{m}(x)dx+c$	$e^x$	$0$	$\frac{1}{m!}x^me^x$
第一类斯特林数	$1$	$n-1$	$\int \hat{G}_{m-1}(x)dx+x\hat{G}_{m}(x)-\int \hat{G}_{m}(x)dx+c$	$1$	$0$	$\frac{1}{m!}\ln(\frac{1}{1-x})^m$
第二类斯特林数	$1$	$m$	$\int \hat{G}_{m-1}(x)dx+m\int \hat{G}_{m}(x)dx+c$	$1$	$0$	$\frac{1}{m!}(e^x-1)^m$
欧拉数	$n-m$	$m+1$	$x\hat{G}_{m-1}(x)-m\int \hat{G}_{m-1}(x)dx+(m+1)\int \hat{G}_{m}(x)dx+c$	$e^x-1$	$0$	推不出来。
完全二分图匹配数	$m$	$1$	$m\int \hat{G}_{m-1}(x)dx+\int \hat{G}_{m}(x)dx+c$	$e^x$	$1$	$(x+1)^me^x$

写了这么老些又臭又长的式子，不知道会不会有笔误，哪里出错了还请指出。